﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

//1.双向链表的实现

// 带头（哨兵位）+双向+循环链表增删查改实现

typedef int LTDataTyp;
typedef struct ListNode
{
	struct ListNode* pre;
	struct ListNode* next;
	LTDataTyp data;
}LTNode;

//创建一个新节点
LTNode* BuyListNode(LTDataTyp x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("BuyListNode::");
		return;
		//或者终止程序：exit（-1）
	}
	//初始化一下，防止野指针的产生
	newnode->next = NULL;
	newnode->pre = NULL;
	newnode->data = x;
	return newnode;
}

//双向链表的初始化
LTNode* LTInit()
{
	LTNode* phead = BuyListNode(-1);
	phead->next = phead;
	phead->pre = phead;
	return phead;
}

//打印双向链表
void LTPrint(LTNode* phead)
{
	assert(phead);
	printf("->head<-");
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("->%d<-", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

//双向链表的尾插
void LTPushBack(LTNode* phead,LTDataTyp x)
{

	assert(phead);
	//申请一个新的节点newnode
	LTNode* newnode = BuyListNode(x);
	//找到尾节点
	LTNode* Tail = phead->pre;

	//这样就把phead，Tail和newnode给连接起来了
	//phead           Tail   newnode
	newnode->pre = Tail;
	Tail->next = newnode;
	newnode->next = phead;
	phead->pre = newnode;
}

//因为链表为空，就没必要删除了，所以增加一个判断是否为空的函数
//判断是否为空（用bool值）
bool LTEmpty(LTNode* phead)
{
	assert(phead);
	//判断phead->next是否和phead相等，相等为真就返回true
	return phead->next == phead;
}

//双向链表的尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	
	LTNode* tail = phead->pre;
	LTNode* tailprev = tail->pre;
	tailprev->next = phead;
	phead->pre = tailprev;
	free(tail);
	tail = NULL;
}

//双链表的头插
void LTPushFront(LTNode* head,LTDataTyp x)
{
	assert(head);
	assert(!LTEmpty(head));

	LTNode* newnode = BuyListNode(x);
	newnode->next = head->next;
	head->next->pre = newnode;
	head->next = newnode;
	newnode->pre = head;

}

//双链表的头删
void LTPopFront(LTNode* head)
{
	assert(head);
	assert(!LTEmpty(head));
	LTNode* delete = head->next;
	LTNode* cur = delete->next;
	head->next = cur;
	cur->pre = head;
	free(delete);
	delete = NULL;
}

//查找双链表中某个值的位置pos
LTNode* LTFind(LTNode* head, LTDataTyp x)
{
	LTNode* cur = head->next;
	while (cur != head)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

//在pos位置之前插入一个节点
void LTInsert(LTNode* pos, LTDataTyp x)
{
	assert(pos);

	LTNode* newnode = BuyListNode(x);
	LTNode* prev = pos->pre;
	//三者位置关系如下
	//prev    newnode    pos
	prev->next = newnode;
	newnode->pre = prev;
	newnode->next = pos;
	pos->pre = newnode;
}

// 双向链表删除pos位置的结点
void ListErase(LTNode* pos)
{
	assert(pos);

	LTNode* prev = pos->pre;
	LTNode* next = pos->next;
	prev->next = next;
	next->pre = prev;
	free(pos);
	pos = NULL;
}

//双向链表的销毁
void LTDestory(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}



//对双向链表的使用
int main()
{
	//创建指针
	LTNode* plist = LTInit();


	//尾插数据
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPushBack(plist, 5);
	LTPushBack(plist, 6);
	LTPushBack(plist, 7);


	//打印双向链表
	LTPrint(plist);

	//尾删
	LTPopBack(plist);
	LTPopBack(plist);

	//打印双向链表
	LTPrint(plist);

	//头插
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);

	//打印双向链表
	LTPrint(plist);

	//头删
	LTPopFront(plist);
	LTPopFront(plist);

	//打印双向链表
	LTPrint(plist);

	//查找值为2的地址，并且删除它
	LTNode* phead = LTFind(plist, 2);
	if (phead)
	{
		ListErase(phead);
		phead = NULL;
	}

	//打印双向链表
	LTPrint(plist);


	//查找值为5的地址，并且在他前面插入100
	LTNode* pp = LTFind(plist, 5);
	if (pp)
	{
		LTInsert(pp, 100);
		pp = NULL;
	}

	//打印双向链表
	LTPrint(plist);

	//销毁双链表
	LTDestory(plist);
	plist = NULL;

	return 0;
}


//2.链表oj题目：

//题目一：复杂链表的复制
//给定一个链表，每个结点包含一个额外增加的随机指针，该指针可以指向链表中的任何结点或空结点。
//要求返回这个链表的深度拷贝

//给你一个长度为n的链表，每个节点包含一个额外增加的随机指针random，该指针可以指向链表中的任何节点或空节点。
//构造这个链表的深拷贝。深拷贝应该正好由n个全新节点组成，
//其中每个新节点的值都设为其对应的原节点的值。新节点的next指针和random指针也都应指向复制链表中的新节点
//并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点
//例如，如果原链表中有X和Y两个节点，其中X.random-- > Y ，
//那么在复制链表中对应的两个节点x和y，同样有x.random-- > y


//思路1：首先将这个链表拷贝下来，先拷贝每个元素和next，然后对于random的指向，就在原链表中找到这个
//元素中random指向的那个元素的相对位置，在它前面的就是负数，在后面的就是正数
//该方法的时间复杂度是O（N²）

//思路2：1.将拷贝节点链接在原节点的后面  2.拷贝每个原节点的random，然后拷贝节点的random就是原节点random
//指向的next  3.拷贝节点剪下来，形成一个新的链表，并且恢复原链表

struct Node 
{
	int val;
	struct Node* next;
	struct Node* random;
};


struct Node* copyRandomList(struct Node* head) 
{
	//1.插入拷贝节点在每一个原节点的后面
	struct Node* cur = head;
	while (cur)
	{
		//插入拷贝节点
		struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
		copy->val = cur->val;
		struct Node* next = cur->next;

		//将cur  copy  next三个指针进行链接
		cur->next = copy;
		copy->next = next;

		cur = next;
	}
	//2.处理每个拷贝节点的random
	cur = head;
	while (cur)
	{
		struct Node* copy = cur->next;
		if (cur->random == NULL)
		{
			copy->random = NULL;
		}
		else
		{
			copy->random = cur->random->next;
		}

		cur = cur->next->next;
	}
	//3.拷贝节点剪下来，连接成新的链表，并且回复原链表
	cur = head;
	struct Node* copyhead = NULL;
	struct Node* copytail = NULL;
	while (cur)
	{
		struct Node* copy = cur->next;
		struct Node* next = copy->next;

		//把copy拿下来尾插
		if (copyhead == NULL)
		{
			copyhead = copytail = copy;
		}
		else
		{
			copytail->next = copy;
			copytail = copytail->next;
		}
		//回复原链表
		cur->next=next;
		cur = next;
	}
	return copyhead;
}







